package Leetcode.动态规划;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/4/4 12:46
 * @Description:
 * 买卖股票的最佳时机 III
 * 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
 *
 * 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 *
 * 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 *
 *
 *
 * 示例 1:
 *
 * 输入：prices = [3,3,5,0,0,3,1,4]
 * 输出：6
 * 解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
 *      随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
 * 示例 2：
 *
 * 输入：prices = [1,2,3,4,5]
 * 输出：4
 * 解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
 *      注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
 *      因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
 * 示例 3：
 *
 * 输入：prices = [7,6,4,3,1]
 * 输出：0
 * 解释：在这个情况下, 没有交易完成, 所以最大利润为 0。
 * 示例 4：
 *
 * 输入：prices = [1]
 * 输出：0
 *
 *
 * 提示：
 *
 * 1 <= prices.length <= 105
 * 0 <= prices[i] <= 105
 */

public class maxProfit {
    public static void main(String[] args) {
        int[] nums = {3, 3, 5, 0, 0, 3, 1, 4};
        System.out.println(maxProfit1(nums));
    }
    /**
     *1.可以双指针遍历，每次找最长的上升序列，然后求一次和存起来  应该算是贪心思想，题意不能用贪心
     * 好像不行3, 3, 5, 0, 0, 3, 1, 4
     * 按理来说应该是0-4  但是这么计算就是只会0-3
     * 但是思路应该没错，可以直接套用之前的股票思路，只是把最多两次的限制条件加进去
     *
     * 好像也不行，因为有这么一个次数的限制条件，假如就是0 0 3 1 4，
     * 答案应该是0-3  1-4  就是6
     * 但是我那么算就只会是0-4 就是4
     * @param prices
     * @return
     */
    public static int maxProfit1(int[] prices) {
        List<Integer> list = new ArrayList<>();
        int len = prices.length;
        if (len == 1) {
            return 0;
        }
        if (len == 2) {
            return Math.max(prices[1] - prices[0], 0);
        }
        int left = 0, right = 0;
        for (int i = 1; i < len; i++) {
            if (prices[i] < prices[i - 1]) {
                int temp = prices[right] - prices[left];
                list.add(temp);
                left = i;
            }
            right++;
        }
        list.add(Math.max(prices[right] - prices[left], 0));
        System.out.println(list);
        if (list.size() <= 2) {
            return list.stream().reduce(0, Integer::sum);
        }
        return list.stream()
                .sorted()
                .skip(list.size() - 2) // 跳过前面的元素，只取最后两个
                .reduce(0, Integer::sum);
    }

    /**
     * 能理解这个思路，但是想不到这个思路
     * @param prices
     * @return
     */
    public static int maxProfit2(int[] prices) {
        int n = prices.length; // 获取价格数组的长度
        int buy1 = -prices[0], sell1 = 0; // 初始化第一次买入和卖出的利润
        int buy2 = -prices[0], sell2 = 0; // 初始化第二次买入和卖出的利润

        // 遍历价格数组，从第二天开始
        for (int i = 1; i < n; ++i) {
            // 更新第一次买入的最大利润（买入价格最低）
            buy1 = Math.max(buy1, -prices[i]);
            // 更新第一次卖出的最大利润（卖出价格最高）
            sell1 = Math.max(sell1, buy1 + prices[i]);

            // 更新第二次买入的最大利润（买入价格最低，考虑第一次卖出的利润）
            //假设第一次利润已经有了，那么我在已有利润上再去买，既sell1 - prices[i]
            //如果是亏得，既<buy2，那么就不买嘛
            buy2 = Math.max(buy2, sell1 - prices[i]);
            // 更新第二次卖出的最大利润（卖出价格最高）
            sell2 = Math.max(sell2, buy2 + prices[i]);
        }
        // 返回两次交易的最大总利润
        return sell2;
    }

}
